λ¬Έμ
κ³λ¨ μ€λ₯΄κΈ° κ²μμ κ³λ¨ μλ μμμ λΆν° κ³λ¨ κΌλκΈ°μ μμΉν λμ°©μ κΉμ§ κ°λ κ²μμ΄λ€. μλμ κ°μ΄ κ°κ°μ κ³λ¨μλ μΌμ ν μ μκ° μ°μ¬ μλλ° κ³λ¨μ λ°μΌλ©΄ κ·Έ κ³λ¨μ μ°μ¬ μλ μ μλ₯Ό μ»κ² λλ€.
μλ₯Ό λ€μ΄ μλμ κ°μ΄ μμμ μμλΆν° 첫 λ²μ§Έ, λ λ²μ§Έ, λ€ λ²μ§Έ, μ¬μ― λ²μ§Έ κ³λ¨μ λ°μ λμ°©μ μ λλ¬νλ©΄ μ΄ μ μλ 10 + 20 + 25 + 20 = 75μ μ΄ λλ€.
κ³λ¨ μ€λ₯΄λ λ°λ λ€μκ³Ό κ°μ κ·μΉμ΄ μλ€.
- κ³λ¨μ ν λ²μ ν κ³λ¨μ© λλ λ κ³λ¨μ© μ€λ₯Ό μ μλ€. μ¦, ν κ³λ¨μ λ°μΌλ©΄μ μ΄μ΄μ λ€μ κ³λ¨μ΄λ, λ€μ λ€μ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€.
- μ°μλ μΈ κ°μ κ³λ¨μ λͺ¨λ λ°μμλ μ λλ€. λ¨, μμμ μ κ³λ¨μ ν¬ν¨λμ§ μλλ€.
- λ§μ§λ§ λμ°© κ³λ¨μ λ°λμ λ°μμΌ νλ€.
λ°λΌμ 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ λ²μ§Έ κ³λ¨μ΄λ, μΈ λ²μ§Έ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€. νμ§λ§, 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ€ λ²μ§Έ κ³λ¨μΌλ‘ μ¬λΌκ°κ±°λ, 첫 λ²μ§Έ, λ λ²μ§Έ, μΈ λ²μ§Έ κ³λ¨μ μ°μν΄μ λͺ¨λ λ°μ μλ μλ€.
κ° κ³λ¨μ μ°μ¬ μλ μ μκ° μ£Όμ΄μ§ λ μ΄ κ²μμμ μ»μ μ μλ μ΄ μ μμ μ΅λκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
- μ λ ₯μ 첫째 μ€μ κ³λ¨μ κ°μκ° μ£Όμ΄μ§λ€.
- λμ§Έ μ€λΆν° ν μ€μ νλμ© μ μΌ μλμ λμΈ κ³λ¨λΆν° μμλλ‘ κ° κ³λ¨μ μ°μ¬ μλ μ μκ° μ£Όμ΄μ§λ€. κ³λ¨μ κ°μλ 300μ΄νμ μμ°μμ΄κ³ , κ³λ¨μ μ°μ¬ μλ μ μλ 10,000μ΄νμ μμ°μμ΄λ€.
μΆλ ₯
- 첫째 μ€μ κ³λ¨ μ€λ₯΄κΈ° κ²μμμ μ»μ μ μλ μ΄ μ μμ μ΅λκ°μ μΆλ ₯νλ€.
π Logic
static int climbStairs() {...}
dp[x][0]μ xμΈ΅ κ³λ¨κΉμ§ κ°λλ° μ°μλ κ³λ¨μ΄ 1κ°μΈ κ²½μ°μ μ΅λ μ μμ΄κ³ ,dp[x][1]μ μ°μλ κ³λ¨μ΄ 2κ°μΈ κ²½μ°μ μ΅λ μ μμ΄λ€.- BOTTOM UPλ°©μμΌλ‘ λͺ¨λ κ³λ¨μ λν μ΅λ μ μλ₯Ό ꡬν μ΄ν, λ§μ§λ§ κ³λ¨μμ λ κ²½μ° μ€ μ΅λκ°μ λ°ννλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] costs;
static int[][] dp;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
costs = new int[N];
dp = new int[N][2];
for (int i = 0; i < N; i++) costs[i] = Integer.parseInt(br.readLine());
System.out.println(climbStairs());
br.close();
}
static int climbStairs() {
if (N == 1) return costs[0];
dp[0][0] = dp[0][1] = costs[0];
dp[1][0] = costs[1];
dp[1][1] = dp[0][0] + costs[1];
for (int i = 2; i < N; i++) {
dp[i][0] = Math.max(dp[i - 2][0], dp[i - 2][1]) + costs[i];
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 2][1]) + costs[i];
}
return Math.max(dp[N - 1][0], dp[N - 1][1]);
}
}
βοΈ Review
- μμ μ C++λ‘ νλ €λ€κ° λͺ» νμ΄μ ν¬κΈ°νλ λ¬Έμ μλ€. μ΄λ² νκΈ° κ³ λ¬Έν΄ μκ°μ DP κ³Όμ μμ μ΄ λ¬Έμ λ³΄λ€ μ‘°κ±΄μ΄ λ μ μ λ¬Έμ λ₯Ό λ§λμ, κ³Όμ λ₯Ό ν΄κ²°ν μ΄ν λ€μ νμ΄λ³΄μλ€.
- "μ°μλ μΈ κ°μ κ³λ¨μ λ°μμ μλλ€"λ 쑰건 λλ¬Έμ κ³ λ―Όνκ³ ,
dp[][0],dp[][1]μ μ΄μ©ν΄μ ν΄λΉ κ³λ¨κΉμ§ μ°μλ κ³λ¨μ΄ 1κ°μΈ κ²½μ°μ 2κ°μΈ κ²½μ°λ₯Ό λλμ΄ κ΅¬ννλ€. - DPλ μ€λ²μΈλ°λ κΌ¬μ΄λ©΄ λ¨Έλ¦¬κ° λ무 μνλ€.